package com.shujujiegou.排序.冒泡选择插入排序算法.插入排序;

/**
 * 直接插入排序基本思想是每一步将一个待排序的记录，
 * 插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
 *
 * 插入排序还分为直接插入排序、二分插入排序、链表插入排序、希尔排序等等，
 * 这里我们只是以直接插入排序讲解，后面讲高级排序的时候会将其他的。
 */
public class InsertSort {
    public static void main(String[] args) {
        // 待排序数组
        int[] array = {8,3,6,2,1,9};

        int j;
        //插入排序
        for(int i= 1; i < array.length; ++i) { // 从下标为1的元素开始选择合适的位置插入，因为下标为0的默认是有序的
            int temp = array[i];
            j = i;

            //  将数组向后挪动
            while(j > 0 && temp < array[j - 1]) { // 从已经排序的最右端进行比较
                array[j] = array[j -1]; // 向后挪动
                j--;
            }

            array[j] = temp; // 从在比其小的数字，插入
        }

        // 打印
        for(int i = 0; i < array.length; ++i) {
            System.out.print(array[i] + " ");
        }
    }
}
